package com.zhupf.part7;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhupf
 * @date 2023年11月20日 15:13
 * @Description
 *
 *  138、随机链表的复制
 */
public class CopyRandomList {

    public static void main(String[] args) {
        Node head7 = new Node(7);
        Node head13 = new Node(13);
        Node head11 = new Node(11);
        Node head10 = new Node(10);
        Node head1 = new Node(1);
        head7.next =head13;
        head13.next = head11;
        head13.random = head7;
        head11.next = head10;
        head10.next = head1;
        head10.random = head11;
        head1.random = head7;
        Node node = copyRandomList2(head7);

    }

    public static Node copyRandomList(Node head) {
        Node res = new Node(0);
        Node tmp = res;
        Map<Node,Node> map = new HashMap<>();
        while (head != null){
            Node copy  = getCopyNode(head,map);
            copy.random = getCopyNode(head.random,map);
            copy.next = getCopyNode(head.next,map);
            tmp.next = copy;
            tmp = tmp.next;
            head = head.next;
        }
        return res.next;
    }

    public static Node copyRandomList2(Node head) {
        Node tmp = head;
        while (tmp != null){
            Node t = tmp.next;
            Node copy = new Node(tmp.val+100);
            tmp.next = copy;
            copy.next = t;
            tmp = t;
        }
        tmp = head;
        while (tmp != null){
            tmp.next.random = tmp.random == null ? null:tmp.random.next;
            tmp = tmp.next.next;
        }
        tmp = head;
        Node res = new Node(0);
        Node dumy = res;
        while (tmp != null){
            Node t = tmp.next.next;
            dumy.next = tmp.next;
            tmp.next = t;
            tmp = t;
            dumy = dumy.next;
        }
        return res.next;
    }

    private static Node getCopyNode(Node node , Map<Node,Node> map){
        if(node == null){
            return null;
        }
        Node copy  = map.get(node);
        if(copy == null){
            copy = new Node(node.val);
            map.put(node,copy);
        }else {
            copy.val = node.val;
        }
        return copy;
    }

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }


}
